Typically, packets of information are routed through a communication network using a networking protocol such as the Internet Protocol (IP), which is a connnectionless networking protocol. In a connectionless networking protocol, each packet of information includes a network layer destination address, and each router forwards a packet of information, based upon the network layer destination address, to the next router on the path. The next router on the path to a particular network layer destination address is predetermined by a routing protocol such as the Open Shortest Path First (OSPF) protocol, the Routing Information Protocol(RIP), or other routing protocol.
Each router makes an independent forwarding decision for the packet based upon its analysis of the network layer destination address in the packet header. Each router determines a next hop for each packet of information based upon the network layer destination address of the packet, and forwards the packet of information to the corresponding next hop (or set of hops) associated with the network layer destination address. Network layer routing, however, requires that each router process each packets' information at the network layer. This operation can be expensive (in terms of computing resources) and time consuming, and can limit the performance of some routers.
Alternatively, packets of information may be routed through a communication network using label switching. Label switching allows a packet to be transported across a network domain using labels rather than the network layer address. A label is a short, fixed length value which represents an forwarding equivalence class (“FEC”). A Label Switched Path (LSP) may be established from an ingress border device to an egress border device in the network domain. The LSP traverses a number of label switching devices. Each label switching device assigns a label to each FEC that it supports. When the packet enters the ingress border device, the ingress border device analyzes the network layer and/or transport layer header of the packet and assigns the packet to a particular FEC. The ingress border device will then insert the corresponding label into the packet, either as a field in the layer 2 header, or as part of a new header inserted between the layer 2 and layer 3 header. Once a packet is assigned a label (and thus an FEC) no further header analysis is done by subsequent label switching devices. Each intermediate label switching device along the LSP makes its forwarding decision for the packet using the label to determine the next hop label and output port for the packet. Each intermediate label switching device will remove the label in the packet and replace it with a label corresponding to the next hop on the label switched path.
It is also possible for a packet to have more than one label (i.e., a label stack). Typically, the label stack is a last-in, first-out stack. When a packet has a label stack, the set of label operations will be the same, i.e., the packet is switched based on the top level of the label stack, except that at some points a label switching device may remove and replace multiple labels or remove the entire label stack. Label stacks allow hierarchical operation or the use of multiple streams within a label switched path.
The Internet Engineering task Force (IETF) Multi-Protocol Label Switching (MPLS) working group has defined an MPLS architecture for utilizing label switching for internetworking. MPLS is considered to be multi-protocol because it can be used with many layer 2 protocols, such as ATM or frame relay, and with any network layer protocol, not just IP. The framework for MPLS is described in an IETF Internet draft document entitled “A Framework for MPLS,” which is referenced as draft-ietf-mpls-framework-05.txt (September 1999), and is herein incorporated by reference in its entirety. The MPLS architecture is described in an IETF Internet draft document entitled “Multiprotocol Label Switching Architecture,” which is referenced as draft-ietf-mpls-arch-06.txt (August 1999), and is hereby incorporated by reference in its entirety.
In order to use label switching for internetworking, each label switching device must learn the labels that are used by its neighboring label switching device(s). Therefore, the IETF MPLS working group has defined a Label Distribution Protocol (LDP) for distributing labels between neighboring label switching devices. LDP may be used to distribute labels between both contiguous and non-contiguous label switching devices. LDP is described in an IETF Internet Draft document entitled “LDP Specification,” which is referenced as draft-ietf-ldp-06.txt (October 1999), and is hereby incorporated by reference in its entirety. There are also other protocols used for label distribution known in the art.
Each label switching device maintains a label information base (LIB) for mapping each FEC to a corresponding label. When the label switching device receives a packet including a label (or label stack), the label switching device utilizes the LIB to map the received label (or the top label of the label stack) to a next hop label and port. The label switching device then replaces the label (or the top label in the label stack) in the packet with the label for the next hop, and forwards the resulting packet to the corresponding outgoing path (or set of paths). In certain situations, when the label switching device is an egress border device, the label switching device will remove the entire label stack.
It may be desirable to set up an LSP which crosses multiple network domains. An LSP which traverses multiple network domains may be desirable for traffic engineering purposes. Traffic engineering is the process of selecting the paths followed by data traffic in a computer network in order to balance the traffic load on the various links, routers, and switches in the network with the goal of reducing congestion and optimizing the use of network resources. MPLS may be used to implement explicitly routed paths to control where the data traffic flows in the network. MPLS traffic engineering routes the traffic flows across a network based on the resources the traffic flow requires and the resources available in the network. Explicitly routed paths may be chosen at or before the time a packet enters the network. In setting up an explicitly routed LSP, it may be desirable to select a route which crosses a non-MPLS domain (i.e., a domain which contains non-MPLS compliant devices).
However, if the network domains traversed by the LSP are not all MPLS domains (i.e. a domain with MPLS compliant devices), any label stack information associated with the packet will be lost when the packet enters the non-MPLS domain (i.e. a domain with non-MPLS compliant devices). The last MPLS compliant device before the non-MPLS domain (i.e., a border device) will remove the entire label stack from the packet before it is sent to the non-MPLS domain. This is not a problem if the label stack includes only one label because this label would be removed at the egress border device of the MPLS domain in any case. However, if the depth of the label stack is greater than 1, all the information in the label stack will be lost when the egress border device of the MPLS domain removes the label stack.